package com.haidechizi.backup.sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{8, 3, 5, 0, 1, 4, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int start, int end) {
        // 当开始位置大于等于结束位置时，结束排序（递归结束条件）
        if (start >= end) {
            return;
        }
        // 记录基准数字
        int position = arr[start];
        // 记录起始位置
        int low = start;
        // 记录结束为止
        int height = end;
        // 结束本次循环的条件
        while (low < height) {
            // 从高位开始比较，当高位的比基准数大时，指针移动
            while (height > low && arr[height] >= position) {
                height--;
            }
            // 高位的数比基准数小，将高位的数赋给低位
            arr[low] = arr[height];
            // 切换到从低位开始比较，当低位的数比基准数小时，指针移动
            while (low < height && arr[low] < position) {
                low++;
            }
            // 低位的数比基准数大时，将低位的数赋值给高位
            arr[height] = arr[low];

        }
        // 次数low = height,将基准数赋值给low（height）
        arr[low] = position;
        // 对分成的两部分数据进行递归排序
        quickSort(arr, start, low);
        quickSort(arr, low + 1, end);

    }
}
